import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/19 17:19
 * @description 快速排序，期望时间复杂度为 O(nlgn)，最坏时间复杂度为 O(n^2)
 * 快速排序的三步分治过程：
 * 1. 分解 A[p..r] -> A[p..q-1] & A[q + 1..r], 其中A[p..q-1]每个元素都小于等于 A[q], A[q+1..r]中每个元素都大于等于A[q]
 * 2. 解决：递归调用快速排序，对A[p..q-1] 和 A[q+1..r]进行排序
 * 3. 合并：由于子数组都有序，所以无需合并
 */
public class QuickSort {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] A = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
        quickSort.quickSort(A, 0, A.length - 1);
        System.out.println(Arrays.toString(A));
    }


    Random random = new Random();
    public void quickSort(int[] A, int p, int r) {
        if (p < r) {
            int q = randomPartition(A, p, r);
            quickSort(A, p, q - 1);
            quickSort(A, q + 1, r);
        }
    }

    /**
     * 随机选择主元
     * @param A A
     * @param p 左边界
     * @param r 有边界
     * @return 划分 index
     */
    public int randomPartition(int[] A, int p, int r) {
        int i = random.nextInt(r - p + 1) + p;
        swap(A, i, r);
        return partition(A, p, r);
    }

    /**
     * 取数组右边界作为主元，然后将数组分为四个部分，
     * 1   |  2 |     3     | 4(r)
     * <=x | >x | 还没有分配 | x
     * @param A 数组A
     * @param p 左边界
     * @param r 右边界
     * @return q
     */
    public int partition(int[] A, int p, int r) {
        // 总是选择 x = A[r]作为主元划分
        int x = A[r], i = p - 1;
        for (int j = p; j < r; j++) {
            if (A[j] <= x) {
                i = i + 1;
                swap(A, i, j);
            }
        }
        swap(A, i + 1, r);
        return i + 1;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}
